#include "game.h"
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)
#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

#define V vector<int>
#define pb push_back
#define si size()

const int N = 10005;

int n, limit;

V c, e[N];

int d[N], d0, bd[N];

struct P {
	int x, y;
	P(int _x = 0, int _y = 0) {
		x = _x, y = _y;
	}
};

P q[N]; int q0;

int r[N];

void dg(int x, int y, int cnt) {
	if(!cnt) return;
	if(x == y) {
		e[q[x].x].pb(q[x].y);
		e[q[x].y].pb(q[x].x);
		r[q[x].x] ++; r[q[x].y] ++;
		return;
	}
	int m = x + y >> 1;
	fo(i, x, m) swap(c[q[i].x], c[q[i].y]);
	int c1 = count(c);
	fo(i, x, m) swap(c[q[i].x], c[q[i].y]);
	dg(x, m, c1); dg(m + 1, y, cnt - c1);
}

int lc[N];

V h[N]; int h0;

void dg(int x) {
	bd[x] = 1;
	d[++ d0] = x;
	ff(j, 0, e[x].si) {
		int y = e[x][j];
		if(!bd[y]) dg(y);
	}
}

void add(int x, int y) {
	if(r[x] < 2 && r[y] < 2) {
		q[++ q0] = P(x, y);
	}
}
std :: vector<int> guess(int _n, int _limit) {
	srand(time(0) + clock());
	n = _n, limit = _limit;
	c.resize(n);
	fo(i, 1, n) c[i - 1] = i;
	do {
		random_shuffle(c.begin(), c.end());
	} while(count(c));
	int jo = 0;
	int n0 = n;
	if(n & 1) {
		jo = 1;
		n ++;
	}
	fo(x, 0, n - 1) {
		q0 = 0;
		ff(i, 0, n - 1) {
			int u = i, v = (n - 1 + x - i) % (n - 1);
			if(v < u) continue;
			if(u == v) {
				if(n - 1 < n0) add(u, n - 1);
			} else add(u, v);
		}
		fo(i, 1, q0) swap(c[q[i].x], c[q[i].y]);
		int c1 = count(c);
		fo(i, 1, q0) swap(c[q[i].x], c[q[i].y]);
		dg(1, q0, c1);
	}
	if(jo) n --;
	ff(i, 0, n) if(!bd[i]) {
		d0 = 0; dg(i);
		h0 ++;
		fo(j, 1, d0) h[h0].pb(d[j]);
	}
	ff(i, 0, n) lc[i] = c[i];
	int c1 = 0;
	fo(i, 1, h0) {
		int m = h[i].si;
		ff(j, 0, m) c[h[i][j]] = lc[h[i][(j + 1) % m]];
		int c2 = count(c);
		if(c1 == c2) {
			ff(j, 0, m) c[h[i][j]] = lc[h[i][j == 0 ? m - 1 : j - 1]];
			c2 += m;
		}
		c1 = c2;
	}
	return c;
}




